package idxRangeAllocer

import (
	"fmt"
	"sort"
	"strconv"
	"strings"
)

// [Down, Up] contain 2 points
type IdxRange struct {
	Id   int64 `json:"id"`
	Down int64 `json:"down"`
	Up   int64 `json:"up"`
}

func (self *IdxRange) Clear() {
	self.Id = 0
	self.Down = 0
	self.Up = 0
}

type IdxRangeList []*IdxRange

func (self IdxRangeList) Len() int {
	return len(self)
}
func (self IdxRangeList) Less(i, j int) bool {
	if self[i] == nil {
		return false
	}
	if self[j] == nil {
		return true
	}
	return self[i].Down < self[j].Down
}
func (self IdxRangeList) Swap(i, j int) {
	self[i], self[j] = self[j], self[i]
}
func (this *IdxRange) String() string {
	s := strings.Join([]string{`{`,
		`id:`, strconv.FormatInt(this.Id, 10), `,`,
		`down:`, strconv.FormatInt(this.Down, 10), `,`,
		`up:`, strconv.FormatInt(this.Up, 10), `,`,
		`}`,
	}, "")
	return s
}

func SortIdxRange(ranges []*IdxRange) {
	sort.Sort(IdxRangeList(ranges))
}

func CheckRangeCross(ranges []*IdxRange) (rlt []*IdxRange, err error) {
	SortIdxRange(ranges)
	nilIdx := 0
	for nilIdx = 0; nilIdx < len(ranges); nilIdx++ {
		if ranges[nilIdx] == nil {
			break
		}
	}
	if nilIdx < len(ranges) {
		ranges = ranges[:nilIdx]
	}

	for i := 0; i < len(ranges); i++ {
		r := ranges[i]
		if r.Down > r.Up {
			return nil, fmt.Errorf("range err, down(%d) > up(%d)", r.Down, r.Up)
		}
		var nextR *IdxRange
		if i != len(ranges)-1 {
			nextR = ranges[i+1]
		}
		if nextR == nil {
			break
		}
		if r.Down >= nextR.Down {
			return nil, fmt.Errorf("range cross err, range a,b, aDown(%d) >= bDown(%d)", r.Down, nextR.Down)
		}
		if r.Up >= nextR.Down {
			return nil, fmt.Errorf("range cross err, range a,b, aDown(%d) < bDown(%d), but aUp(%d) >= bDown(%d)", r.Down, nextR.Down, r.Up, nextR.Down)
		}
	}
	return ranges, nil
}

func CheckRangeCrossWithoutGap(ranges []*IdxRange) error {
	for i := 0; i < len(ranges); i++ {
		if ranges[i] == nil {
			return fmt.Errorf("ranges[%d] is nil elem", i)
		}
	}
	_, err := CheckRangeCross(ranges)
	if err != nil {
		return err
	}
	sum := int64(0)
	for i := 0; i < len(ranges); i++ {
		sum += ranges[i].Up - ranges[i].Down + 1
	}
	if sum != ranges[len(ranges)-1].Up-ranges[0].Down+1 {
		return fmt.Errorf("ranges are not filled without gap")
	}
	return nil
}

func IteratorSortedIdxRange(ranges []*IdxRange, down int64, up int64, proc func(id int64) bool) {
	if down > up {
		return
	}

	found := false
	for i := 0; i < len(ranges); i++ {
		r := ranges[i]
		if down <= r.Down && r.Up <= up {
			found = true
			if !proc(r.Id) {
				return
			}
		} else {
			// 因为是顺序的范围, 所以一旦已经找到过元素后又不在范围了, 说明后面的都在范围外了, 直接结束
			if found {
				return
			}
		}
	}
}

func GetSortedIdxRangeByIdx(ranges []*IdxRange, idx int64) *IdxRange {
	rlen := len(ranges)
	if rlen == 0 {
		return nil
	}
	if idx < ranges[0].Down || ranges[rlen-1].Up < idx {
		return nil
	}

	for i := 0; i < rlen; i++ {
		r := ranges[i]
		if idx < r.Down {
			return nil
		}
		if idx <= r.Up {
			return r
		}
	}
	return nil
}

var ErrNeedExtendIdxSpace = fmt.Errorf("left idx space is not enough, should extend")

func AllocIdxRanges(allocedIdxRanges []*IdxRange, newID int64, minIdx int64, maxIdx int64, newAllocCount int64) (rlt []*IdxRange, err error) {
	var allRanges []*IdxRange
	allRanges = append(allRanges, &IdxRange{Down: minIdx - 1, Up: minIdx - 1})
	for i := 0; i < len(allocedIdxRanges); i++ {
		rSrc := allocedIdxRanges[i]
		if rSrc != nil && rSrc.Up >= minIdx && rSrc.Down <= maxIdx {
			r := &IdxRange{Down: rSrc.Down, Up: rSrc.Up, Id: rSrc.Id}
			if r.Down < minIdx {
				r.Down = minIdx
			}
			if r.Up > maxIdx {
				r.Up = maxIdx
			}
			allRanges = append(allRanges, r)
		}
	}
	allRanges = append(allRanges, &IdxRange{Down: maxIdx + 1, Up: maxIdx + 1})

	// sort allRanges
	allRanges, err = CheckRangeCross(allRanges)
	if err != nil {
		return nil, err
	}

	unAllocCnt := newAllocCount
	for i := 0; i < len(allRanges); i++ {
		if unAllocCnt <= 0 {
			break
		}

		r := allRanges[i]
		var nextR *IdxRange
		if i != len(allRanges)-1 {
			nextR = allRanges[i+1]
		}
		if nextR == nil {
			break
		}

		if nextR.Down-r.Up > 1 {
			down := r.Up + 1
			up := nextR.Down - 1
			if nextR.Down-r.Up-1 > unAllocCnt {
				up = r.Up + unAllocCnt
			}
			unAllocCnt -= up - down + 1

			rlt = append(rlt, &IdxRange{Down: down, Up: up, Id: newID})
		}
	}

	if unAllocCnt > 0 {
		return nil, ErrNeedExtendIdxSpace
	}

	return
}
